/*
 * Separator.cpp
 *
 *  Created on: Jan 24, 2014
 *      Author: ik
 */

#include <Separator.h>
#include <ExactCliqueLifter.h>
#include <ApproxCliqueLifter.h>
#include <Desigualdad.h>
#include <RDCliquer.h>
#include <OsterCliquer.h>
#include <BitParallelCliquer.h>
#include <TimeLimit.h>
#include <list>
#include <stack>

#include <cstdio>

using namespace std;

Cliquer * Separator::createCliquer(TiposCliquer tipo, bool clqOrStab) {
	Cliquer * ret;
	switch (tipo) {
		case Goloso:
			ret = new CliquerGoloso(_actual, _grafo, clqOrStab);
			break;
		case BitParallel:
			ret = new BitParallelCliquer(_actual, clqOrStab);
			break;
		case RD:
			ret = new RDCliquer(_actual, clqOrStab);
			break;
		default:
			break;
	}

	return ret;
}

Separator::Separator(Grafo &grafo, SeparatorParameters &param) :
		_n(grafo.getN()), _iteration(0), _proyeccionFuerte(param.PROJTYPE==Fuerte), _ncortes(1), _ncliques(0), _nllamadas(0),
		_nrangos(0), _nprangos(0), _rondasSinReserva(0), _esReserva(true), _grafo(grafo), _falso(NULL),
		_actual(*(new Proyectable(_n))), _eleccionClqFactory(NULL), _clique(new ProjectableCliqueSet(_n)), _lastClique(new ProjectableCliqueSet(_n)),
		_cliqueados(new VertexSet(_n)), _nocliqueados(new VertexSet(_n)), _verticesRestantes(new VertexSet(_n)),
		_parametros(param),	_K(param.K), _desigualdades(), _reserva(new ReservaClique(_n)), _lastVal(grafo.getN()), _ninoperante(0)
{
	_buscadorVioladas = createCliquer(param.buscadorDeCliquesVioladas, true);
	_calculadorLambda = createCliquer(param.calculadorDeLambda, false);
}

Separator::~Separator()
{
	delete &_actual;
	delete _buscadorVioladas;
	delete _calculadorLambda;
	delete _clique;
	delete _lastClique;
	delete _cliqueados;
	delete _nocliqueados;
	delete _verticesRestantes;

	if (_reserva != NULL)
		delete _reserva;

	if (_falso != NULL)
		delete _falso;
}

void Separator::restart()
{
	_iteration = 0;
	_ncortes = 1;
	_ncliques= 0;
	_nllamadas = 0;
	_nrangos = 0;
	_nprangos = 0;
	_rondasSinReserva = 0;
	_esReserva = true;
	_ninoperante = 0;
	_K = _parametros.K;
}

list<Desigualdad*>& Separator::separarReserva(Solucion &solucion) {
	if (_esReserva)
	{
		_nllamadas++;
		if (_lastVal - solucion.value() < _parametros.MINVIOLATION)
			_ninoperante++;
		else
			_ninoperante = 0;

		_rondasSinReserva++;

		_desigualdades.clear();
		if (TimeLimit::getInstance().limitReached() || _ninoperante >= 10 || _rondasSinReserva > 20) {
			_ncortes = 0;
			_ninoperante = 0;
//			_rondasSinReserva = _rondasSinReserva-2;
//			if (_reserva != NULL && _rondasSinReserva > 20)
//			{
//				_reserva->haceInactiva();
//			}
			return _desigualdades;
		}
		_ncortes = 0;
	}

	list<ProjectableCliqueSet *> violista;
	int found = 0;
//	if (_reserva->buscaVioladas(solucion, -_parametros.MINVIOLATION-0.2, 10, violista) > 0) {
	if (_reserva->buscaCliqueVioladas(solucion, -0.35, 20, violista) > 0) {
		if (_esReserva)
			_eleccionClqFactory = new GeneradorClique(&solucion.fracVertices(), &solucion);
		GeneradorClique * eleccionClq2 = _eleccionClqFactory->newInstance(&_actual, &_parametros);
		int r = _reserva->cliqueVioladas();
		_ncliques += r;
		_ncortes += r;
		int max = solucion.nfracVertices()/10;
		if (max < 6)
			max = 6;
		for (list<ProjectableCliqueSet *>::iterator it = violista.begin(); it != violista.end(); it++) {
//			bool estaViolada = ((*it)->valor(solucion) >= 1.0+0.25*_parametros.MINVIOLATION);
			bool estaViolada = ((*it)->weight() >= 1.0+_parametros.MINVIOLATION);
			if (estaViolada) {
				_reserva->agregaClique(*(*it));
				_desigualdades.push_back(desigualdadClique(*(*it)));
				_rondasSinReserva = 0;
				found++;
				//				(*it)->print();
			}
			else if (found < max)
			{
				_actual.copySubgrafo(_grafo, solucion.fracVertices());
				Desigualdad * ret = separarLifteando(*(*it), solucion, *eleccionClq2);
				if (ret) {
//					if (!estaViolada && ret->getSoporte().intersects(*(*it)))
//						_reserva->agregaClique(*(*it));
					//				cout << "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ EU TE DISSE 0 !!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;
					//				clique.print();
					//				ret->print();
					//				cout << "VALOR CLIQUE: " << clique.weight() << " VALOR CORTE: " << ret->valor(solucion) << " MINVIO: " << _parametros.MINVIOLATION << endl;
					_desigualdades.push_back(ret);
					_rondasSinReserva = 0;
					if (ret->isRank())
						_nrangos++;
					else
						_nprangos++;
				}
				else
					delete (*it);
			}
		}

		delete eleccionClq2;
		if (_esReserva)
			delete _eleccionClqFactory;
	}

	_lastVal = solucion.value();
	return _desigualdades;
}

//procedimiento para separar
list<Desigualdad*>& Separator::separar(Solucion &solucion)
{
	_nllamadas++;
	if (_lastVal - solucion.value() < _parametros.MINVIOLATION)
	{
		if (++_ninoperante >= 2*_K && _ninoperante >= 5)
		{
			_ncortes = 0;
//			_ninoperante = 0;
			_desigualdades.clear();
			return _desigualdades;
		}
	}
	else
		_ninoperante = 0;
	_desigualdades.clear();
//	if (TimeLimit::getInstance().limitReached() || _ncortes == 0 || _ninoperante >= 10) {
//		_ncortes = 0;
//		_ninoperante = 0;
//		return _desigualdades;
//	}

	_ncortes = 0;
	_esReserva = false;

	_eleccionClqFactory = new GeneradorClique(&solucion.fracVertices(), &solucion);

	ProjectableCliqueSet * clq_ptr = new ProjectableCliqueSet(_n);

	bool hayCliques = (_K != 0) && (_iteration % _K == 0) && _reserva->hayClique();
	if (hayCliques)
	{
		separarReserva(solucion);
		_ncortes += separarCliques(*clq_ptr, solucion, false);
	}
	else
	{
		_ncortes += separarCliques(*clq_ptr, solucion, true);
		if (_ncortes == 0)
			separarReserva(solucion);
	}
//	if (_ncortes == 0)
//		_ncortes += separarRango(*clq_ptr, solucion);

	if (_ncortes >= 10)
		_iteration++;
	else
	{
		if (_K > 1)
			--_K;
		_iteration = _K;
	}

	delete clq_ptr;
	delete _eleccionClqFactory;
	_esReserva = true;

	_lastVal = solucion.value();
	return _desigualdades;
}

int Separator::separarCliques(ProjectableCliqueSet& clique, Solucion &solucion, bool conRango) {
	int found = 0;
	GeneradorClique * eleccionClq = _eleccionClqFactory->newInstance(&_grafo, &_parametros);
	GeneradorClique * eleccionClq2 = _eleccionClqFactory->newInstance(&_actual, &_parametros);

	int sinrango = 0;

	_verticesRestantes->copyAll(solucion.fracVertices());
	int max = conRango ? solucion.nfracVertices()/10 : solucion.nfracVertices()/5;
	if (max < 6)
		max = 6;

	while (!_verticesRestantes->isEmpty() && found < max) {
		clique.removeAll();
		eleccionClq->cliqueSueltaMaximal(_verticesRestantes, &clique);

		if (clique.weight() >= 1.0+0.25*_parametros.MINVIOLATION) {
			_reserva->agregaClique(clique);
			Desigualdad * ret = desigualdadClique(clique);
			_desigualdades.push_back(ret);
			_ncliques++;
			found++;
		}
		else if (clique.size() >= 2 && clique.weight() >= 0.65)
		{
			if (clique.weight() >= 0.85)
				_reserva->agregaClique(clique);
			if (conRango && sinrango < max/3) {
				_actual.copySubgrafo(_grafo, solucion.fracVertices());
				Desigualdad * ret = separarLifteando(clique, solucion, *eleccionClq2);
				if (ret) {
					//				if (ret->getSoporte().intersects(clique)) {
					//					if (clique.size() > 2)
					//						_reserva->agregaClique(clique);
					//				}
					//				cout << "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ EU TE DISSE 3 !!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;
					//				clique.print();
					//				ret->print();
					//				cout << "VALOR CLIQUE: " << clique.weight() << " VALOR CORTE: " << ret->valor(solucion) << " MINVIO: " << param.MINVIOLATION << endl;
					_desigualdades.push_back(ret);
					if (ret->isRank())
						_nrangos++;
					else
						_nprangos++;
					found++;
					sinrango = 0;
				}
				else sinrango++;
			}
		}
		_verticesRestantes->removeAll(clique);
	}
	delete eleccionClq;
	delete eleccionClq2;
	return found;
}

int Separator::separarRango(ProjectableCliqueSet& clique, Solucion &solucion) {
	GeneradorClique * eleccionClq = _eleccionClqFactory->newInstance(&_actual, &_parametros);
	int nsinvioladas = 0;
	int found = 0;

	bool hadNext = true;
	int max = solucion.nfracVertices()/10;
	if (max < 2)
		max = 2;
	while (nsinvioladas < _parametros.MAXITER && found < max && hadNext && eleccionClq->hasNext() && ! TimeLimit::getInstance().limitReached())
	{
		_actual.copySubgrafo(_grafo, solucion.fracVertices());
		bool hayClique;
		if (_proyeccionFuerte)
			hayClique = eleccionClq->cliqueNonArista(&clique) || eleccionClq->nextClique(&clique);
		else
			hayClique= eleccionClq->nextCliqueMaximal(&clique);
		if (hayClique) {
//			if (!_actual.isClique(clique))
//			{
//				cout << "No es clique -- nextClique:" << endl;
//				clique.print();
//				exit(0);
//			}

			int clqf;
			if (clique.weight() >= 1.0+(0.25*_parametros.MINVIOLATION))
			{
				_desigualdades.push_back(desigualdadClique(clique));
				_ncliques++;
				_ncortes++;
				found++;
				clqf = 1;
			}
			else
				clqf = 0;

			int cr = -_ncliques - _nrangos - _nprangos;
			Desigualdad * ret = separarLifteando(clique, solucion, *eleccionClq);
			if (ret) {
				if (ret->getSoporte().intersects(clique))
					_reserva->agregaClique(clique);
				_desigualdades.push_back(ret);
				if (ret->isRank()) {
					_nrangos++;
//					cout << "CP-R[" << param.MAXCLIQUESZ << "]";
//					ret->print();
				}
				else {
					_nprangos++;
//					cout << "CP-GR[" << param.MAXCLIQUESZ << "]";
//					ret->print();
				}
			}
			else if (clique.size() >= 2 && clique.weight() >= 0.85)
					_reserva->agregaClique(clique);
			cr += _ncliques + _nrangos + _nprangos;

			if (cr || clqf) {
				nsinvioladas = 0;
				if (cr > 0) {
					_ncortes+=cr;
					found+=cr;
				}
//				cout << cr+clqf << endl;
			}
			else
				nsinvioladas++;
		}
		else
			hadNext = false;
	}
	delete eleccionClq;

	return found;
}

//separa lifteando a partir de una clique
Desigualdad * Separator::separarLifteando(ProjectableCliqueSet& cliqueInicial, Solucion &solucion, GeneradorClique& eleccionClique)
{
	if (_K == 0)
		return NULL;

	_clique->copyAll(cliqueInicial, cliqueInicial.size(), cliqueInicial.weight());
	vector<CliqueProyectada *> proyecciones;
	proyecciones.reserve(_K);

	if (_falso == NULL)
		_falso = new Grafo(_n);

	Desigualdad* ret = 0;
	bool hayFalsas = _proyeccionFuerte ? _actual.proyectarCliqueFuerte(*_clique, solucion.fracVertices(), *_falso) : _actual.proyectarClique(*_clique, solucion.fracVertices(), *_falso);
	if (!hayFalsas)
		return ret;

	int nivel = 0;

	_cliqueados->removeAll();
	_nocliqueados->copyAll(solucion.fracVertices());
	_nocliqueados->removeAll(*_clique);
	_lastClique->copyAll(*_clique, _clique->size(), _clique->weight());

	proyecciones.push_back(new CliqueProyectada(_clique, _falso));
	_clique->removeAll();
	_falso = NULL;
	nivel++;
	int iclq = _ncliques;

	int i = 0;
	while (ret == NULL && (nivel >= 1) && ((nivel <= 2*_K) || (i % _K != 0)) && i <= 3*_K && _ncliques - iclq < 3 && !TimeLimit::getInstance().limitReached())
	{
		if (++i % _K == 0)// && nivel > _K)
		{
//			cout << "." << endl;
			ret = buscarCliqueViolada(solucion, *_clique);
			if (ret != NULL && _grafo.isClique(*_clique))
			{
				_desigualdades.push_back(ret);
				_ncliques++;
//				delete ret;
				ret = NULL;
			}
			if (ret != NULL)
				_clique->removeAll();
		}
//		else
//			cout << "-" << endl;

		if (ret == NULL && ((nivel <= 2*_K) || (i % _K != 0)))
		{
			int v;
			if (_clique->size() == 0) {
//				_cliqueados->removeAll();
				for (int w = 0; w < _lastClique->lista().cantidad(); w++)
					_cliqueados->addAll(_actual.vecinos(_lastClique->lista()[w]));
				_cliqueados->retainAll(*_nocliqueados);
				if (_proyeccionFuerte)
				{
					if (!eleccionClique.cliqueNonArista(_clique))
						eleccionClique.cliqueSuelta(_cliqueados, _clique);
				}
				else
					eleccionClique.cliqueSueltaMaximal(_cliqueados, _clique);
			}
			if (_clique->size() < 2)
				nivel = INT_MAX;
			else
				_lastClique->copyAll(*_clique, _clique->size(), _clique->weight());

//			if (!_actual.isClique(*clique))
//			{
//				cout << "No es clique -- nivel:" << nivel << endl;
//				clique->print();
//				exit(0);
//			}

			if (_clique->weight() >= 1.0+(_parametros.MINVIOLATION)) {
				if (_grafo.isClique(*_clique))
				{
					_desigualdades.push_back(desigualdadClique(*_clique));
					_ncliques++;
				}
				else if (nivel > _K || _clique->weight() <= 1.0+2*_parametros.MINVIOLATION) {
					ret = desigualdadClique(*_clique);
					_clique->removeAll();
					if (_falso == NULL)
						_falso = new Grafo(_n);
				}
			}

			if (ret == NULL && nivel < INT_MAX) {
				if (_falso == NULL)
					_falso = new Grafo(_n);

				bool hayFalsas = _proyeccionFuerte ? _actual.proyectarCliqueFuerte(*_clique, solucion.fracVertices(), *_falso) : _actual.proyectarClique(*_clique, solucion.fracVertices(), *_falso);
				if (hayFalsas)
				{
//					cout << "=";
//					if (!_actual.isClique(*clique))
//					{
//						cout << "No es clique -- nivel:" << nivel << endl;
//						clique->print();
//						exit(0);
//					}

					nivel++;
					proyecciones.push_back(new CliqueProyectada(_clique, _falso));

					_falso = NULL;
				}
				else
				{
//					cout << "|";

					_actual.restituir(_falso);
					_falso->clear();
				}
				_nocliqueados->removeAll(*_clique);
				_clique->removeAll();
			}
		}
	}

	LIFT:

	CliqueLifter * lifter = NULL;
	if (ret && (_clique->size() == 0))
	{
		if (_proyeccionFuerte)
			lifter = new ApproxCliqueLifter(_actual, *_calculadorLambda, _parametros);
		else
			lifter = new ExactCliqueLifter(_actual, *_calculadorLambda);
	}

	//deshacer proyecciones
	if (ret != NULL && lifter != NULL)
	{
		bool estaViolada = true;
		while(estaViolada && !proyecciones.empty())
		{
//			ret->print();

			nivel--;

			CliqueProyectada* proyectada = proyecciones[proyecciones.size()-1];

			_actual.borrar(proyectada->getGrafoFalso());

			lifter->lift(ret, proyectada);
//			lifter->lift(ret, proyecciones);

			proyecciones.pop_back();
			estaViolada = ret->estaViolada(solucion, _parametros.MINVIOLATION);
			//			if (estaViolada)
			//				cout << "+" << endl;
			//			else
			//				cout << "-" << endl;

			if (_proyeccionFuerte)
				_actual.restituir(proyectada->getGrafoFalso());
			delete proyectada;
		}
		delete lifter;

		if (!estaViolada) {
			delete ret;
			ret = NULL;
		}
//		else if (!ret->esValida(_actual))
//		{
//			cout << "Desigualdad no es válida para _actual -- nivel:" << nivel << endl;
//			if (!ret->esValida(_grafo))
//			{
//				cout << "Desigualdad no es válida para _grafo -- nivel:" << nivel << endl;
//			}
//			else
//				cout << "Desigualdad ES válida para _grafo -- nivel:" << nivel << endl;
//			//			if (!_actual.isClique(*proyectada))
//			//				cout << "No es clique en _actual!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;
//			//			if (!_grafo.isClique(*proyectada))
//			//				cout << "No es clique en _grafo!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;
//			//
//			//			proyectada->print();
//			ret->print();
//			solucion.fracVertices().print();
//			exit(0);
//			estaViolada = false;
//		}

	}

	while(!proyecciones.empty())
	{
		CliqueProyectada* proyectada = proyecciones[proyecciones.size()-1];
		proyecciones.pop_back();
		delete proyectada;
	}

	return ret;
}

Desigualdad* Separator::buscarCliqueViolada(Solucion &solucion, ProjectableCliqueSet& clique)
{
	double b = 1.05 + _parametros.MINVIOLATION;
	_buscadorVioladas->optimize(solucion, solucion.fracVertices(), clique, b-0.01, b+.05, 0.045);

	if (clique.weight() <= b) {
//		clique.removeAll();
		return NULL;
	}

	return desigualdadClique(clique);
}

Desigualdad* Separator::desigualdadClique(ProjectableCliqueSet& clique)
{
	Desigualdad* ret = newDesigualdad();
	Lista& lc = clique.lista();
	for (int i = 0; i < lc.cantidad(); i++)
		ret->setCoeficiente(lc[i],1);

	ret->setRHS(1);
	ret->setAsRank();

	return ret;
}
